package Tree;

public class item105 {
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null) return null;
        TreeNode root = build(preorder,0,preorder.length-1,
                inorder ,0,inorder.length-1);

        return root;
    }

    private static TreeNode build(int[] preorder,int leftp,int rightp,
                           int[] inorder,   int lefti,int righti)
    {
        if(leftp>rightp||lefti>righti) return null;
        TreeNode root = new TreeNode(preorder[leftp]);
        int index =0;
        for (int i = lefti; i <=righti ; i++) {
            if(preorder[leftp]==inorder[i])
            {
                index = i;
                break;
            }
        }
        int len = index-leftp;
        root.left = build(preorder,leftp+1,leftp+len,inorder,lefti,index-1);
        root.right = build(preorder,leftp+len+1,rightp,inorder,index+1,righti);
        return root;
    }
//[3,9,20,15,7]
//        [9,3,15,20,7]
    public static void main(String[] args) {
        int [] pre ={1,2,3};
        int [] in ={3,2,1};
        buildTree(pre,in);
    }
}
